#include "fibonacciHeap.h"
#include <iostream>
#include <cmath>

FibonacciHeap::FibonacciHeap()
{
	name = 0;
	dist = 0;
	cut = false;
	parent = NULL;

}
FibonacciHeap::FibonacciHeap(int n, int d)
{
	name = n;
	dist = d;
	cut = false;
	parent = NULL;

}

void RootList::meld(RootList h2)
{
	//append list of roots h2 in rootList
	//if(!h2.roots.empty()){
	numMeld++;
		roots.splice(roots.end(), h2.roots);
		if(min == NULL)
			min = h2.min; 
		else
			min = min->getDist() > h2.min->getDist() ? h2.min : min;
	//}else cout << "meld h2 is empty" << endl;
}

void RootList::incert(FibonacciHeap c)
{
	RootList aux;
	FibonacciHeap *p = new FibonacciHeap();
	*p = c;

	aux.roots.push_back(p);
	aux.min = p;
	meld(aux);
	numNodes++;

	if(c.getName()+1 > (int)pos.size()){
                for(int i = pos.size(); i <= c.getName(); i++){
                        pos.push_back(NULL);
                }
        }
	pos[p->getName()] = p;
}

void RootList::incertV(Vertex c)
{
        RootList aux;
	numMeld = 0;
        FibonacciHeap *p = new FibonacciHeap(c.getName(), c.getDist());

        aux.roots.push_back(p);
        aux.min = p;
        meld(aux);
        numNodes++;

        if(c.getName()+1 > (int)pos.size()){
                for(int i = pos.size(); i <= c.getName(); i++){
                        pos.push_back(NULL);
                }
        }
        //cout << c.getName() << " " << c.getDist() << " " << &c << endl;
        pos[p->getName()] = p;
}


void FibonacciHeap::printHeap()
{
	cout << name << " " << dist << endl;
	for(list<FibonacciHeap*>::iterator it = children.begin(); it != children.end(); it++){
		(*it)->printHeap();
	}
}


FibonacciHeap* RootList::getMin()
{
	return min; 
}

RootList::RootList()
{
	min = NULL;
	numNodes = 0;
	numDeletemin = 0;
	numCut = 0;
	numMeld = 0;
}

void RootList::printHeap()
{
	cout << " Print Heap" << endl;
	for(list<FibonacciHeap*>::iterator it = roots.begin(); it != roots.end(); it++){
                (*it)->printHeap();
	}
}

void RootList::Cut(FibonacciHeap *x)
{
	//if(x == NULL) {
	//	cout << "Cut parm null" << endl;
	//	exit(1);
	//}
	numCut++;
	FibonacciHeap *p = x->parent;
	//if(p->children.empty()) cout << "Child not found" << endl;
	//else {		
		roots.push_back(x);
		x->parent = NULL;
		p->children.remove(x);
	//}
}

void RootList::Cascading_Cut(FibonacciHeap *p)
{
	//if(p == NULL){
	//	cout << "Cascading Cut null param" << endl;
	//	exit(1);
	//}
	FibonacciHeap *aux;
	if(p->parent != NULL){ //if isnt a root node
		if(!p->cut){
			p->cut = true;
		} else {
			aux = p->parent;
			p->cut = false;
			Cut(p);
			Cascading_Cut(aux);
		}
	}
}

void RootList::decreasekey(FibonacciHeap e, int c)
{
	FibonacciHeap *aux=NULL, *p=NULL;
	numCut = 1;
	if(e.getDist() < c) cout << "new key is greater then current key" << endl;
	else {
		p = pos[e.getName()];
		//if(p == NULL || (e.getName() != p->getName())){
		//	cout << "Decrease key error" << endl;
		//	exit(1);
		//}
		p->setDist(c);
		if(c < min->getDist()) min = p;
		
		if(p->parent != NULL){ //not root
			if(p->parent->getDist() > p->getDist()){
				aux = p->parent;
				p->cut = false;
				Cut(p);
				Cascading_Cut(aux);	
			}
		}
	}
}

void RootList::decreasekeyV(Vertex e, int c)
{
        FibonacciHeap *aux=NULL, *p=NULL;
        numCut = 1;
	if(e.getDist() < c) cout << "new key is greater then current key" << endl;
        else {
                p = pos[e.getName()];
                //if(p == NULL || (e.getName() != p->getName())){
                //        cout << "Decrease key error" << endl;
                //        exit(1);
                //}
                p->setDist(c);
                if(c < min->getDist()) min = p;

		if(p->parent != NULL){ //not root
			if(p->parent->getDist() > p->getDist()){
                                aux = p->parent;
                                p->cut = false;
                                Cut(p);
                                Cascading_Cut(aux);
                        }
		}
        }
}

void RootList::printPos()
{
	for(int i = 0; i < pos.size(); i++)
        	if(pos[i] != NULL) cout << pos[i]->getName() << endl;
}

FibonacciHeap RootList::deletemin()
{
	vector<FibonacciHeap*> r;
	FibonacciHeap *aux = NULL, ret;
	numDeletemin = 0;

	int M = ceil((log(numNodes)/log(1.618))); //posto maximo
	int degree;
	
	ret.setDist(min->getDist());
	ret.setName(min->getName());
	removeMin();

	for(int i =0 ; i <= M; i++){
		numDeletemin++;
		r.push_back(NULL);
	}

	for(list<FibonacciHeap*>::iterator it = roots.begin();
		it != roots.end(); it++)
	{	
		(*it)->parent = NULL;
		degree = (*it)->children.size();
		aux = *it;
		while(r[degree] != NULL) {
			aux = link(aux, r[degree]);
			r[degree] = NULL;
			degree++;
			//if(degree > M){
			//	cout << "deletemin error" << endl;
			//	exit(1);
			//}
		}
		r[degree] = aux;
	}
	roots.clear();
	for(int i = 0; i < r.size(); i++)
	{
		numDeletemin++;
		if(r[i] != NULL) 
		{
			roots.push_back(r[i]);
			if(min == NULL) min = r[i];
			else if(min->getDist() > r[i]->getDist()) min = r[i];
		}
	}	 
	return ret;
}

void RootList::removeMin()
{
	roots.remove(min);
        roots.splice(roots.end(), min->children);

	//for(list<FibonacciHeap*>::iterator it = roots.begin();
        //        it != roots.end(); it++){
        //        (*it)->parent = NULL;
	//}
	pos[min->getName()] = NULL;
        delete min;
	numNodes--;
	min = NULL;
}

Vertex RootList::deleteminV()
{
        vector<FibonacciHeap*> r;
        FibonacciHeap *aux = NULL;
	Vertex ret;
	numDeletemin = 0;

        //int M = ceil((log(numNodes)/log(1.5)) + 2); //posto maximo
        int M = ceil((log(numNodes)/log(1.618))); //posto maximo
        int degree;
	
	if(numNodes == 0){
		cout << "Heap vazio" << endl;
		exit(1);
	}	
 
        ret.setDist(min->getDist());
        ret.setName(min->getName());
	removeMin();

        for(int i =0 ; i <= M; i++){
                r.push_back(NULL);
		numDeletemin++;
	}

        for(list<FibonacciHeap*>::iterator it = roots.begin();
                it != roots.end(); it++)
        {
                (*it)->parent = NULL;
		degree = (*it)->children.size();
                aux = *it;
                while(r[degree] != NULL) {
                        aux = link(aux, r[degree]);
			r[degree] = NULL;
                        degree++;
                        //if(degree > M){
                        //        cout << "deletemin error" << endl;
                        //        exit(1);
                        //}
                }
                r[degree] = aux;
        }
        roots.clear();
        for(int i = 0; i < r.size(); i++)
        {
        	numDeletemin++;
	        if(r[i] != NULL)
                {
                        roots.push_back(r[i]);
                        if(min == NULL) min = r[i];
                        else if(min->getDist() > r[i]->getDist()) min = r[i];
                }
        }
        return ret;
}


FibonacciHeap* RootList::link(FibonacciHeap *h1, FibonacciHeap *h2)
{
	//if(h1 == NULL || h2 == NULL){
	//	cout << "link error" << endl;
	//	exit(1);
	//}
	numDeletemin++;
	FibonacciHeap *ret;
	if(h1->getDist() < h2->getDist()){
		h2->parent = h1;
		h1->parent = NULL;
		h1->children.push_back(h2);
		ret = h1;
	} else {
		h1->parent = h2;
		h2->parent = NULL;
		h2->children.push_back(h1);
		ret = h2;
	}

	h1->cut = false;
	h2->cut = false;
	return ret;
}
